/*
 * @lc app=leetcode.cn id=21 lang=cpp
 *
 * [21] 合并两个有序链表
 */

// @lc code=start

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *cur_node = new ListNode();
        ListNode *head = cur_node;
        while (list1 != nullptr || list2 != nullptr)
        {
            if (list1->val < list2->val)
            {
                ListNode *next_node1 = new ListNode();
                next_node1->val = list1->val;
                cur_node->next = next_node1;
                cur_node = cur_node->next;
                list1 = list1->next;
            }
            else if (list1->val == list2->val)
            {
                ListNode *next_node1 = new ListNode();
                next_node1->val = list1->val; // 这样是深拷贝
                cur_node->next = next_node1;  // 这样是浅拷贝
                cur_node = cur_node->next;
                list1 = list1->next;
                ListNode *next_node2 = new ListNode();
                next_node2->val = list2->val;
                cur_node->next = next_node2;
                cur_node = cur_node->next;
                list2 = list2->next;
            }
            else
            {
                ListNode *next_node2 = new ListNode();
                next_node2->val = list2->val;
                cur_node->next = next_node2;
                cur_node = cur_node->next;
                list2 = list2->next;
            }
        }
        return head->next;
    }
};
// @lc code=end
